// 冒泡排序
/**
 * 冒泡排序：重复走访需要排序的数列，一次比较两个元素，如果顺序错误就交换
 * 
 * 算法描述：
 *  1. 比较相邻的元素，如果第一个比第二个大就交换【所以最后一个是最大的】
 *  2. 重复步骤
 * 
 * 
 * 复杂度：
 *  时间复杂度： O(n^2)
 *  空间复杂度： O(1)
 * 
 * 
 * 稳定性：在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。
 * 
 * **/ 

function bubbleSort(arr) {
    for (let i = arr.length; i >= 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j+1], arr[j]]
            };
        };
    };

    return arr;
};


const arr = [1, 3, 7, 4, 2, 6];

console.log(bubbleSort(arr));


// 代码优化
/***
 *  优化点：swap标志，当前一轮没有交换的时候就说明数组已经有序，没必要进行下一轮循环
 * */ 

function bubbleSort1(arr) {
    let swap;

    for (let i = arr.length; i >= 0; i--) {
        swap = false;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j+1], arr[j]]
                swap = true;
            }
        };

        if (swap === false) {
            break;
        };
    };

    return arr;
};

console.log(bubbleSort1(arr));